home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 March: Reference Library / Dev.CD Mar 96 RL / Dev.CD Mar 96 RL.toast / Technical Documentation / develop / develop Issue 25 / develop Issue 25 code / NURBs / Listing 2 - Knot insertion.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-11-20  |  2.5 KB  |  96 lines  |  [TEXT/CWIE]
  1. #include <QD3DGeometry.h>
  2. #include <stdlib.h>
  3.  
  4. static TQ3NURBCurveData *InsertKnot
  5.     (TQ3NURBCurveData        *oldCurveData,    // Old curve
  6.      float                     tNew)            // Knot to insert
  7.  
  8. {
  9.     TQ3NURBCurveData        *newCurveData;    // New curve after adding knot
  10.     unsigned long            k;                // Order of curve
  11.     unsigned long            n;                // Number of control points
  12.     TQ3RationalPoint4D        *b;                // Old control point vector
  13.     TQ3RationalPoint4D        *bHat;            // New control point vector
  14.     float                    *x;                // Old knot vector
  15.     float                    *xHat;            // New knot vector
  16.     float                    alpha;            // Interpolation ratio
  17.     unsigned long            i;                 // Knot to insert after
  18.     unsigned long            j;                // Knot index for search
  19.     TQ3Boolean                foundIndex;        // Insertion index found?
  20.     
  21.     // Set up local variables for readability.
  22.     k = oldCurveData->order;
  23.     n = oldCurveData->numPoints;
  24.     x = oldCurveData->knots;
  25.     b = oldCurveData->controlPoints;
  26.     
  27.     // Allocate space for new control points and knot vector.
  28.     bHat = malloc((n + 1) * sizeof(TQ3RationalPoint4D));
  29.     xHat = malloc((n + k + 1) * sizeof(float));
  30.     
  31.     // Allocate data structure for new curve.
  32.     newCurveData = malloc(sizeof(TQ3NURBCurveData));
  33.     newCurveData->order = k;
  34.     newCurveData->numPoints = n + 1;
  35.     newCurveData->controlPoints = bHat; 
  36.     newCurveData->knots = xHat;
  37.     newCurveData->curveAttributeSet = 
  38.         (oldCurveData->curveAttributeSet == NULL)
  39.                         ? NULL
  40.                         : Q3Object_Duplicate(oldCurveData->curveAttributeSet);
  41.     
  42.     // Find where to insert the new knot. 
  43.     for (j = 0, foundIndex = kQ3False; j < n + k; j++) {
  44.         if (tNew > x[j] && tNew <= x[j + 1]) {
  45.             i = j;
  46.             foundIndex = kQ3True;
  47.             break;
  48.         }
  49.     }
  50.     
  51.     // Return if not found.
  52.     if (!foundIndex) {
  53.         return (NULL);
  54.     }
  55.     
  56.     // Copy knots to new vector.
  57.     for (j = 0; j < n + k + 1; j++) {
  58.         if (j <= i) {
  59.             xHat[j] = x[j];
  60.         } else if (j == i + 1) {
  61.             xHat[j] = tNew;
  62.         } else {
  63.             xHat[j] = x[j - 1];
  64.         }
  65.     }
  66.  
  67.     // Compute position of new control point and new positions
  68.     // of existing ones.
  69.     for (j = 0; j < n + 1; j++) {
  70.         if (j <= i - k + 1) {
  71.             alpha = 1;
  72.         } else if (i - k + 2 <= j && j <= i) {
  73.             if (x[j + k - 1] - x[j] == 0) {
  74.                 alpha = 0;
  75.             } else {
  76.                 alpha = (tNew - x[j]) / (x[j + k - 1] - x[j]); 
  77.             }
  78.         } else {
  79.             alpha = 0;
  80.         }
  81.         
  82.         if (alpha == 0) {
  83.             bHat[j] = b[j - 1];
  84.         } else if (alpha == 1) {
  85.             bHat[j] = b[j];
  86.         } else {
  87.             bHat[j].x = (1 - alpha) * b[j - 1].x + alpha * b[j].x;
  88.             bHat[j].y = (1 - alpha) * b[j - 1].y + alpha * b[j].y;
  89.             bHat[j].z = (1 - alpha) * b[j - 1].z + alpha * b[j].z;
  90.             bHat[j].w = (1 - alpha) * b[j - 1].w + alpha * b[j].w;
  91.         }
  92.     }
  93.     
  94.     return (newCurveData);
  95. }
  96.